#pragma once

template<class K>
struct BSTreeNode
{
	typedef BSTreeNode<K> Node;
	K _key;
	Node* _left;
	Node* _right;

	BSTreeNode(const K& key)
	{
		_key = key;
		_left = nullptr;
		_right = nullptr;
	}

};

template<class K>
class BSTree
{
	typedef BSTreeNode<K> Node;
public:
	BSTree() = default;

	BSTree(const BSTree<K>& t)
	{
		_root = Copy(t._root);
	}

	Node* Copy(Node* root)
	{
		if (root == nullptr)
			return nullptr;
		Node* newRoot = new Node(root->_key);
		newRoot->_left = Copy(root->_left);
		newRoot->_right = Copy(root->_right);

		return newRoot;
	}

	BSTree<T>& operator=(BSTree<K> t)
	{
		swap(_root, t._root);
		return *this;
	}

	void Inorder()
	{
		_Inorder(_root);
		cout << endl;
	}

	void _Inorder(Node* root)
	{
		if (root == nullptr)
			return;
		_Inorder(root->_left);
		cout << root->_key << " ";
		_Inorder(root->_right);
	}

	~BSTree()
	{
		Destroy(_root);
	}

	void Destroy(Node* root)
	{
		if (root == nullptr)
			return;
		Destroy(root->_left);
		Destroy(root->_right);
		delete root;
	}

	

private:
	Node* _root = nullptr;

};